// 695. 岛屿的最大面积
// 给你一个大小为 m x n 的二进制矩阵 grid 。
//
// 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
//
// 岛屿的面积是岛上值为 1 的单元格的数目。
//
// 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

// void dfs()//参数用来表示状态  
// {  
//     if(到达终点状态)  
//     {  
//         ...//根据题意添加  
//         return;  
//     }  
//     if(越界或者是不合法状态)  
//         return;  
//     if(特殊状态)//剪枝
//         return ;
//     for(扩展方式)  
//     {  
//         if(扩展方式所达到状态合法)  
//         {  
//             修改操作;//根据题意来添加  
//             标记；  
//             dfs（）；  
//             (还原标记)；  
//             //是否还原标记根据题意  
//             //如果加上（还原标记）就是 回溯法  
//         }  
 
//     }  
// }
// 原文链接：https://blog.csdn.net/qq_40763929/article/details/81629800
/**
 * @param {number[][]} grid
 * @param i
 * @param j
 * @return {number}
 */
// function dfs(grid, i, j) {  // 对于每一个岛屿，计算其面积
//   if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === 0) {  // 如果超出边界或者是水，则返回0
//     return 0;
//   }
//   grid[i][j] = 0; // 将该点设置为0，表示已经访问过
//   return 1 + dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1); // 对于每一个岛屿，计算其面积
// }
// var maxAreaOfIsland = function(grid) {
//   let max = 0;  // 最大岛屿面积
//   for (let i = 0; i < grid.length; i++) { // 行
//     for (let j = 0; j < grid[0].length; j++) {  // 对于每一个点
//       if (grid[i][j] === 1) {
//         max = Math.max(max, dfs(grid, i, j)); // 对于每一个岛屿，计算其面积
//       }
//     }
//   }
//   return max;
// };

function dfs(grid, i, j) {  // 对于每一个岛屿，计算其面积
  //
  // if (grid[i][j] === 0 || i > grid.length-1 || j > grid[0].length-1 || i < 0||j<0) {
  if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === 0) {
    return 0;
  }
  grid[i][j] = 0; 
  return 1 + dfs(grid, i, j + 1) + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j - 1);
}
var maxAreaOfIsland = function(grid) {
  let max = 0;
  for (let i = 0; i < grid.length; i++){
    for (let j = 0; j < grid[0].length; j++){
      if (grid[i][j] === 1) {
      max = Math.max(max, dfs(grid, i, j));
      }
    }
  }
  return max;
};
console.log(
    maxAreaOfIsland(
        [[0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
              [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
              [0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0],
              [0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]]));